package com.hatcher.cvte.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 多叉树类
 */
public class Tree {

	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static void main(String[] args) {
		// 读取层次数据结果集列表
		List dataList = Util.getVirtualResult();
		// 节点列表（映射表，用于临时存储节点对象）
		HashMap nodeList = new HashMap();
		// 根节点
		Node root = null;
		// 将结果集存入映射表（后面将借助映射表构造多叉树）
		for (Iterator it = dataList.iterator(); it.hasNext();) {
			Map dataRecord = (Map) it.next();
			Node node = new Node();
			node.id = (String) dataRecord.get("id");
			node.text = (String) dataRecord.get("text");
			node.parentId = (String) dataRecord.get("parentId");
			nodeList.put(node.id, node);
		}
		// 构造无序的多叉树
		Set entrySet = nodeList.entrySet();
		for (Iterator it = entrySet.iterator(); it.hasNext();) {
			Node node = (Node) ((Map.Entry) it.next()).getValue();
			if (node.parentId == null || node.parentId.equals("")) {
				root = node;
			} else {
				((Node) nodeList.get(node.parentId)).addChild(node);
			}
		}
		// 输出无序的树形结构的JSON字符串
		System.out.println(root);
		// 对多叉树进行横向排序
		root.sortChildren();
		// 输出有序的树形结构的JSON字符串
		System.out.println(root);
	}
}

/**
 * 节点类
 */
class Node {
	/**
	 * 节点编号
	 */
	public String id;
	/**
	 * 节点内容
	 */
	public String text;
	/**
	 * 父节点编号
	 */
	public String parentId;
	/**
	 * 孩子节点列表
	 */
	@SuppressWarnings("rawtypes")
	private List children = new ArrayList();

	// 添加孩子节点
	@SuppressWarnings("unchecked")
	public void addChild(Node node) {
		children.add(node);
	}

	// 先序遍历，拼接JSON字符串
	public String toString() {
		String result = "{" + "id : '" + id + "'" + ", text : '" + text + "'";
		if (children.size() != 0) {
			result += ", children : [";
			for (int i = 0; i < children.size(); i++) {
				result += ((Node) children.get(i)).toString() + ",";
			}
			result = result.substring(0, result.length() - 1);
			result += "]";
		} else {
			result += ", leaf : true";
		}
		return result + "}";
	}

	// 兄弟节点横向排序
	@SuppressWarnings("unchecked")
	public void sortChildren() {
		if (children.size() != 0) {
			// 对本层节点进行排序（可根据不同的排序属性，传入不同的比较器，这里 传入ID比较器）
			Collections.sort(children, new NodeIDComparator());
			// 对每个节点的下一层节点进行排序
			for (int i = 0; i < children.size(); i++) {
				((Node) children.get(i)).sortChildren();
			}
		}
	}
}

/**
 * 节点比较器
 */
@SuppressWarnings("rawtypes")
class NodeIDComparator implements Comparator {
	// 按照节点编号比较
	public int compare(Object o1, Object o2) {
		int j1 = Integer.parseInt(((Node) o1).id);
		int j2 = Integer.parseInt(((Node) o2).id);
		return (j1 < j2 ? -1 : (j1 == j2 ? 0 : 1));
	}
}
